package 算法.查找.散列表;

import com.sun.org.apache.regexp.internal.recompile;

/**
 * 【散列表：线性探测法】
 * 	注：为了保证能将所有的键都存储，必须保证M>N
 * @Date   2017-09-02
 * @author Administrator
 * @version TODO:>>>>>>>尚未测试
 */
public class LinearProbingHashST<Key, Val> {
	private int M = 16;					    //散列表数组长度（可以存储的键的总个数）
	private int N;							//记录当前共存有几个key
	private Key[] keys;
	private Val[] vals;
	public LinearProbingHashST() {
		keys = (Key[])new Object[M];
		vals = (Val[])new Object[M];
	}
	
	private void resize() {
		//TODO:为数组扩容
	}
	
	/**
	 * calHashByKey()：计算key的hash值
	 * 	特定算法。。别纠结了。。
	 * @return
	 */
	public int calHashByKey(Key k) {
		return (k.hashCode() & 0x7fffffff) % M;
	}
	
	/**
	 * put()：线性探测 
	 * @param k
	 * @param v
	 */
	public void put(Key k, Val v) {
		if (N >= M/2)	resize();
		int hash;
		for (hash=calHashByKey(k); keys[hash]!=null; hash = (hash+1)%M) 
			if (keys[hash].equals(k)) {vals[hash] = v;	return;}
		keys[hash] = k;
		vals[hash] = v;
		N++;
	}
	
	/**
	 * get()：
	 * @param k
	 */
	public Val get(Key k) {
		for(int hash = calHashByKey(k); keys[hash] != null; hash = (hash+1)%M)
			if (keys[hash].equals(k)) return vals[hash];
		return null;
	}
} 
